package com.jhy.review.day02;

import com.jhy.review.day01.Node;

/**
 * 实现满二叉树
 * 动态规划 dp实现
 * 什么是树形dp
 * 你解答一个题的时候 你可以通过左树要信息和右树要信息
 * 把你的事情解决了。就可以用这个套路。
 *
 * 举一个例子：
 * 一个二叉树的中位数的信息
 * 就不能用树形dp 左边要一个中位数 右边要一个中位数 不好解答
 * 只是面试的时候好用，因为好区分
 * 2022年7月21日15:25:18
 */
public class FullBinaryTree {

    public static boolean isF(Node head) {
        if (head == null) {
            return true;
        }

        Info data = process(head);

        return data.nodes == (1 << data.height - 1 );
    }
    public static class Info {
        // 信息体告诉我们 高度和个数
        public int height;
        public int nodes;
        public Info(int height, int nodes) {
            this.height = height;
            this.nodes = nodes;
        }
    }

    public static Info process(Node node){
        if(node==null){
            return new Info(0,0);
        }
        Info leftData = process(node.left);
        Info rightData = process(node.right);

        // 当前节点总体的高度
        int height = Math.max(leftData.height,rightData.height)+1;
        // 当前一共有几个节点数据
        int nodes = leftData.nodes + leftData.nodes + 1 ;
        return new Info(height,nodes);

    }


}
